1. Field
The present disclosure relates to the allocation of registers the scheduling of instructions, and, more specifically, to the classifying of operands and allocation of registers to local operands.
2. Background Information
Compilers and other translation systems typically transform one set of symbols into another by following a set of syntactic and semantic rules. Two of the actions often performed by a compiler include scheduling instructions and allocating registers. The compiler typically determines in what order a set of instructions will be executed. Also, the compiler typically allocates registers for use by the instructions.
Most optimizing compliers perform the phases of register allocation and code scheduling as separate steps. However, because the first step is not aware of the limitations of the second step, the optimizations made in the second step are usually unnecessarily constrained by the incorrect assumptions made in the first step. As such, the scheduling and register allocation stages may be integrated.
Integrating the scheduling and register allocation may decrease compilation times. Compile time saving may be obtained by sharing some of the data structures between the scheduler and the register allocation, and from not having to reschedule blocks of instruction with spill operations.
A register, in this context, may be a set of bits of high-speed memory within a processor or other electronic device, used to hold data for a particular purpose. Typically registers are considered the closest memory available to a processor. Registers typically include two types: scratch and preserved registers. Often when a set of instructions calls a second set of instructions (hereafter, “calls a function”), the contents of the registers used by the first set of instructions may be replaced or overwritten with values used by the called function. When the function exits and returns control back to the first set of instructions, some of the values that the function replaced are expected to be restored back to the state that existed before the function was called. These registers, which are restored, are referred to as “preserved registers” because the values of the registers are preserved across a function call. Scratch registers, conversely, are typically not preserved across a function call. The values of a scratch registers are generally discarded when the function is called.
Often processors do not contain enough registers to hold the values needed to fully execute a set of instructions and any functions that may be called. Therefore, register values are frequently copied from the registers to a higher level of memory (e.g. cache or system memory). The operation of copying registers to memory is often referred to as a “spill.” The opposite operation of copying memory to the register is known as a “fill.” While some spills and fills are to be expected, attempts are often made to minimize the occurrences. Each spill/fill involves inserting a number of unproductive instructions into the set of instructions and, occasionally, idling the processor as it waits for the information to be transferred.
One of the problems associated with allocating a register during scheduling is making an optimal choice between using a scratch or a preserved register. If a preserved register is used, its original contents will have to be saved before the register is first used and restored after its last use within the function. If a scratch register is used to store a value that lives across a function call, special instructions will have to be used to save and restore the register value before and after the call. These saves and restores from memory impact performance.
The “lifetime” of a value is typically defined as the time between when the value is first defined or used, and the last time it is used. When a first instruction that defines or uses a value is scheduled, a register needs to be immediately allocated to the value. Otherwise, for example, the scheduler will not be able to properly anticipate any needed spills or fills if it does not known the number of registers in use. However, at this point, it is not always known whether or not the lifetime of that value will interfere with a function call. To minimize spills/fills, a scratch register is preferred, if the value will not live across a function call. However, if the value will live across a call, a preserved register if typically preferred.